1. Field of the Invention
The present invention relates to digital cellular communication systems, and more particularly, to a method and apparatus for the encryption of data communications within such a system.
2. History of the Prior Art
Cellular radio communications is, perhaps, the fastest growing field in the world-wide telecommunications industry. Although cellular radio communication systems comprise only a small fraction of the telecommunications systems presently in operation, it is widely believed that this fraction will steadily increase and will represent a major portion of the entire telecommunications market in the not too distant future. This belief is grounded in the inherent limitations of conventional telephone communications networks which rely primarily on wire technology to connect subscribers within the network. A standard household or office telephone, for example, is connected to a wall outlet, or phone jack, by a telephone cord of a certain maximum length. Similarly, wires connect the telephone outlet with a local switching office of the telephone company. A telephone user's movement is thus restricted not only by the length of the telephone cord, but also by the availability of an operative telephone outlet, i.e. an outlet which has been connected with the local switching office. Indeed, the genesis of cellular radio systems can be attributed, in large part, to the desire to overcome these restrictions and to afford the telephone user the freedom to move about or to travel away from his home or office without sacrificing his ability to communicate effectively with others. In a typical cellular radio system, the user, or the user's vehicle, carries a relatively small, wireless device which communicates with a base station and connects the user to other mobile stations in the system and to landline parties in the public switched telephone network (PSTN).
A significant disadvantage of existing cellular radio communication systems is the ease with which analog radio transmissions may be intercepted. In particular, some or all of the communications between the mobile station and the base station may be monitored, without authorization, simply by tuning an appropriate electronic receiver to the frequency or frequencies of the communications. Hence, anyone with access to such a receiver and an interest in eavesdropping can violate the privacy of the communications virtually at will and with total impunity. While there have been efforts to make electronic eavesdropping illegal, the clandestine nature of such activities generally means that most, if not all, instances of eavesdropping will go undetected and, therefore, unpunished and undeterred. The possibility that a competitor or a foe may decide to "tune in" to one's seemingly private telephone conversations has heretofore hindered the proliferation of cellular radio communication systems and, left unchecked, will continue to threaten the viability of such systems for businesses and government applications.
It has recently become clear that the cellular radio telecommunications systems of the future will be implemented using digital rather than analog technology. The switch to digital is dictated, primarily, by considerations relating to system speed and capacity. A single analog, or voice, radio frequency (RF) channel can accommodate four (4) to six (6) digital, or data, RF channels. Thus, by digitizing speech prior to transmission over the voice channel, the channel capacity and, consequently the overall system capacity, may be increased dramatically without increasing the bandwidth of the voice channel. As a corollary, the system is able to handle a substantially greater number of mobile stations at a significantly lower cost.
Although the switch from analog to digital cellular radio systems ameliorates somewhat the likelihood of breeches in the security of communications between the base station and the mobile station, the risk of electronic eavesdropping is far from eliminated. A digital receiver may be constructed which is capable of decoding the digital signals and generating the original speech. The hardware may be more complicated and the undertaking more expensive than in the case of analog transmission, but the possibility persists that highly personal or sensitive conversations in a digital cellular radio system may be monitored by a third party and potentially used to the detriment of the system users. Moreover, the very possibility of a third party eavesdropping on a telephone conversation automatically precludes the use of cellular telecommunications in certain government applications. Certain business users may be equally sensitive to the possibility of a security breech. Thus, to render cellular systems as viable alternatives to the conventional wireline networks, security of communications must be available on at least some circuits.
Once a decision has been made to protect the transmission of digital information (data) from unauthorized access, the originator (sender) and the intended recipient (receiver) of the data must agree on a secret mechanism for enciphering (encrypting) and deciphering (decrypting) the information. Such an agreement usually involves a mutual commitment to use a particular encryption device which may be widely available, but which can be programmed with a secret key specific to the sender and receiver. The agreement, however, must also include choices with respect to the encryption technique and the method of synchronization to be used by the encryption device.
Several encryption techniques are known and implemented by prior art encryption devices. In one such technique, known as "block substitution", the secret key bits are mixed with blocks of data bits to produce blocks of encrypted data. With block substitution, blocks of data bits which differ merely by a single bit produce encrypted data blocks which differ, on the average, in one half (1/2) of their bit positions and vise versa. Similarly, encrypted data blocks differing only in one bit position will produce decrypted data blocks differing, on the average, in one half (1/2) of their bit positions. This type of encryption/decryption tends to magnify the effects of bit errors which may occur upon transmission of the encrypted data and, therefore, is not an appropriate technique for use in digital radio communications.
Another known encryption technique relies on a keystream generator and modular arithmetic or finite math. A plurality of secret key bits and a series of clock pulses are applied to the keystream generator which generates a stream of pseudo-random bits referred to as a keystream. The keystream bits are then bit-by-bit modulo-2 added to the data bits prior to transmission by the sender. An identical keystream generator is used by the receiver to produce an identical keystream of bits which are then bit-by-bit modulo-2 subtracted from the received encrypted data stream to recover the original data. Proper implementation of this technique requires that the sender and receiver keystream generators be synchronized so that the keystream generated at the receiver and subtracted from the encrypted data is in harmony with the keystream generated at the sender and added to the original data.
An encryption technique which generates a large number of complex keystream bits and which may be implemented in a general purpose Arithmetic and Logic Unit (ALU) is disclosed in co-pending U.S. patent application Ser. No. 556,358, entitled "Encryption System For Digital Cellular Communication", first mentioned above. The present invention is directed to a related but distinct aspect of an encryption system, generally, the synchronization of the encryption and decryption of data transmitted over an RF link and, more specifically, the synchronization of encryption and decryption upon handoff in a duplex cellular radio system.
A variety of approaches to the issue of synchronization may be found in prior art encryption systems. In most encryption systems, synchronization may be viewed as an agreement between the sender and the receiver on the number of clock pulses to be applied from a common initial state until the generation of a particular bit. Other prior art encryption systems, however, do not keep a running count of the number of applied clock pulses and rely, instead, on the initialization of the sender and receiver to the same state at the beginning of a frame and the application of an identical number of clock pulses thereafter. The shortcoming of the latter scheme is the difficulty of reestablishing synchronization should the sender and receiver fall out of synchronization during a particular frame.
Yet another type of encryption system includes a counter which maintains a count of the number of keystream bits, or blocks of keystream bits, previously generated. The output bits of the counter are combined with the secret key bits to generate the keystream. Because the transmitter and receiver counters are incremented on a regular basis and, therefore, take on the characteristics of a digital time/date clock, such an encryption system is often referred to as a time-of-day driven encryption system.
The advantage of the time-of-day driven encryption system resides in the fact that if the receiver counter falls out of synchronization with the transmitter counter and the system has the capability of providing the receiver with the current transmitter counter value, the receiver counter may be immediately reset to the transmitter counter value instead of returning to the beginning and applying the entire history of clock pulses. The difficulty with such a system, however, is the provision of the transmitter counter value on a sufficiently frequent basis to avoid the accumulation of errors caused by the divergence of the receiver counter value from the transmitter counter value for a relatively long period of time.
A continuous synchronization technique which may be used to synchronize a time-of-day encryption system and to prevent the aforementioned accumulation of errors is disclosed in co-pending U.S. patent application Ser. No. 556,102, entitled "Continuous Cipher Synchronization For Cellular Communication System", and first referenced above. The present invention is directed to a method and apparatus for resynchronization of an encryption system upon "handoff" of communications between cells of a duplex cellular radio system, i.e., a cellular radio system in which enciphered digital communication traffic is simultaneously sent from a base station to a mobile station and from the mobile station to the base station.
Because each of the cells in a cellular radio system may be relatively small in size, the likelihood of one of the mobile stations travelling out of one cell and into another cell is great. As the mobile stations travel through the cellular system, they may reach the radio coverage limit of one cell and, therefore, be better served by another cell. The process of switching an established call from one cell to another is known as handoff. The cellular system usually tracks each mobile station and assesses the need for a handoff by periodically measuring the signal strength of the surrounding base stations. If the measured signal strength of the base station presently serving the mobile station falls below a predetermined level, the cellular system determines the availability of other channels in neighboring cells and transmits a command to the mobile station, via a high speed data message interrupting the speech communications on the voice channel (a blank and burst data message), to retune to a frequency which is available in a new cell. The mobile station mutes the speech and tunes to the radio channel indicated in the blank and burst data message. Speech transmission is resumed after the mobile station has tuned to the new channel.
Handoffs between base stations in a cellular radio system may also occur for reasons other than the limitations in the radio coverage of a base station. For example, handoff may be performed because of excessive interference in a channel, traffic congestion at a base station or for a variety of other reasons which render handoff advisable or necessary. It should be noted, moreover, that handoffs may also take place between different cellular systems in order to maintain a call as a mobile station passes from the radio coverage area of one cellular system to another, and possibly unrelated, cellular system.
A number of complications are introduced to the process of handoff when transmissions in the cellular system are digitized and encrypted. One practical problem arises from the fact that the encryption system counter in one base station may be completely out of synchronization with the corresponding counter in another base station. This is particularly true with respect to base stations operated by commercially distinct, and often competing, entities. The issue in terms of handoff is how to ascertain the counter value at the new base station with a minimum of interruption to the speech stream. It should be noted in this connection that the base station must be the "master" as far as the count value is concerned. Otherwise, if the mobile station was the master, then each base station would be required to maintain a large number of counter values, one for each mobile station being served by the base station. Designating the mobile station as the master would thus preclude the use of time-sharing and cost-reducing hardware. It is desirable, instead, to have a single universal counter value in each base station which may be used to synchronize all of the mobile stations being served by the base station. In sum, upon handoff, the new base station must transmit to the mobile station the new counter value which may then be used, if necessary, to reset the counter in the mobile station.
Another practical problem in performing handoff of an encrypted telephone conversation is caused by transmission delays in the communications between elements in the land network, for example, between the base stations and a mobile switching center (MSC) which coordinates the operation of the cellular system. Such delays may prevent the mobile station from tuning to the new base station frequency at exactly the same time that the new base station begins broadcasting the new counter value. In particular, the blank and burst data message commanding the mobile station to tune to a new base station frequency is usually sent by the MSC to the old base station and relayed to the mobile station. At the same time, the MSC signals the new base station to begin broadcasting the new counter value. However, the transmission delays in the communications link between the MSC and the old base station are not necessarily the same as the transmission delays in the communications link between the MSC and the new base station. For example, the former communications link may not have the same number of signal repeaters as the latter communications link. Hence, there could be a period of uncertainty from the time the mobile station becomes tuned to the new base station frequency and the time that the new base station begins broadcasting the new counter value.
One objective of the present invention is to minimize the interruption of the speech or voice traffic flow upon handoff by providing a first means for rapidly resynchronizing a mobile station with a new base station and a second means for ensuring resynchronization should the first rapid means fail to achieve resynchronization. The interruption of speech traffic upon handoff may be further minimized in accordance with the present invention where the cellular system includes a mechanism for synchronization of the respective base stations.